package 力扣进阶面试题;

import 力扣题库.TreeNode;


public class p105从前序与中序遍历构造二叉树 {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder==null || inorder==null) {
            return null;//只知道一个遍历结果无法构建二叉树
        }

        TreeNode root =buildTreeChild(preorder,inorder,0,inorder.length-1);
        return root;

    }

    public static int preindex=0;
    public TreeNode buildTreeChild(int[] preorder, int[] inorder,int inbegin,int inend) {
        if (inbegin>inend) {
            return null;//左树或右树为空
        }
        //二叉树的根
        TreeNode root=new TreeNode(preorder[preindex]);

        //在中序中 找二叉树的根
        int rootIndex=findRootIndex(inorder,inbegin,inend,preorder[preindex]);
        preindex++;

        //构建左子树
        root.left=buildTreeChild(preorder,inorder,inbegin,rootIndex-1);
        //构建右子树
        root.right=buildTreeChild(preorder,inorder,rootIndex+1,inend);
        return root;
    }
    //找 当前根节点在中序中的下标
    public int findRootIndex(int[] inorder,int inbegin,int inend,int key) {
        for (int i = inbegin; i <=inend; i++) {
            if (inorder[i]==key) {
                return i;
            }
        }
        return -1;
    }
}
